// Justin Cowen
// CSC 332 - Data Structures
// April 18, 2010
// Program #5
// This program uses the QueueAr class and the various methods associated with it
// to read in a list of integers into a Directed Graph. This program uses an adjacency
// matrix to hold the value of the edges of the directed graph. It uses the printDF and 
// printBF methods incorporating recursion in order to do a Depth-First and Breadth-First 
// Traversal of the graph. This program is interactive and based on user input.
//

import java.io.*;
import java.util.*;


class Graph{
    
	private static int n;  // the number of vertices. The vertex set will be {0, 1, . ,n.1}.
    private static boolean[][]edge;  // edge[i][j] = true if and only if there is
	                                 // a directed edge from vertex i to vertex j
    private static boolean[]used;  // for the traversals to keep track of vertices that have
	                               // already been visited. used[i] = true is true if and only 
	                               // if vertex i has been used
    private QueueAr<Integer> q;  // Queue for the breadth-first traversal. 
	
    public Graph(){ //constructor
        BufferedReader keyboard = new BufferedReader (new InputStreamReader (System.in));
        StringTokenizer st;
        String line;
        int first, second; // Vertices in an arc
        System.out.print("Enter the number of vertices: ");
        try{
             n = Integer.parseInt (keyboard.readLine());
        } catch(NumberFormatException e){} catch(IOException f) {};
        System.out.println();
        used = new boolean[n];
        edge = new boolean[n][n];
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++){
                edge[i][j] = false;
            }
        }    
        
        
        System.out.println("Vertex set = 0 to " + (n-1));
        System.out.println("Enter edges, one per line. Enter -1 to stop.");
        System.out.println("For example: 1 2 will create the directed edge from 1 to 2");
        try{
             while(true){ // Keep reading until a -1 is read.
                 line = keyboard.readLine();
                 st = new StringTokenizer(line);
                 first = Integer.parseInt (st.nextToken());
                 if (first == -1) return;
                 second = Integer.parseInt (st.nextToken());
                 edge[first][second]=true;
             }
        }catch(NumberFormatException e){} catch(IOException f){}
    }
	
    public void printBF(){    // Driver for the depth first traversal
    	System.out.println("\nBreadth-First Print:");
        q = new QueueAr();    // Create the queue 
    	q.makeEmpty();        // make it empty
        for(int i=0; i<n; i++){  //Initialize the array used to all false
            used[i]=false;
        }
        for (int i=0; i<n; i++){  // For each vertex i if i has not been 
            if(used[i]==false){   // used call the printBF  method on i
                printBF(i); 
                System.out.print("\n");
            }
        } 
    }
	
    public void printBF(int i){
        q.enqueue(i);  //Enqueue i
        used[i]=true;  //set used[i] to true
        while(q.isEmpty()!=true){    // while the queue is not empty, 
            int k = q.dequeue();     // dequeue k
            System.out.print(k+" "); // print k
            for(int j=0; j<n; j++){  // for each vertex j
                if(edge[k][j]==true&&used[j]!=true){ //if there's a directed edge not used
                    q.enqueue(j);    //enqueue j
                    used[j]=true;    // set used[j] to true
                }
            }
        }
    }

    public void printDF(){    // The driver for the depth-first print. 
    	System.out.print("Vertex Set == ");
        for(int j=0; j<n; j++){       // loop to print the Vertex Set
            System.out.print(j+", ");            
        }
        System.out.print("\n");
        System.out.print("Edge Set == ");
        for(int j=0; j<n; j++){       // loop to print the Edge set
            for(int h=0; h<n; h++){
                if(edge[j][h]==true){
                	System.out.print(j+"-->"+h+",");
                }
            }
        }
        System.out.print("\n\n");
        System.out.println("Depth-First Print:");
        
        for(int i=0; i<n; i++){// Initialize the array used to all false.
            used[i]=false;
        }
        
        for (int i=0; i<n; i++){   //For each vertex i, if i has not been used,
            if(used[i]==false){    //then call the printDF method on i
                printDF(i); 
                System.out.println();
            }
        } 
       
    }
	
    public void printDF(int i){ // Recursive workhorse    	
        used[i]=true;	 // set used[i] to true
        System.out.print(i+" ");  // print vertex i
        for(int j=0; j<n; j++){   // for each vertex j
            if(edge[i][j]==true && used[j]==false){ // if there's a directed edge not used
                printDF(j); // print j
            }
        }
    }
}

class Prog5{
	public static void main (String[] args){
        Graph g = new Graph();        
        System.out.println("");
        g.printDF();
        g.printBF();
    }
}
